লিঙ্কড লিস্টের ধারণা এবং প্রকারভেদ: Singly, Doubly, Circular Linked List

লিঙ্কড লিস্টের ধারণা

লিঙ্কড লিস্ট হলো একটি ডেটা স্ট্রাকচার যেখানে ডেটা উপাদানগুলো একটি ধারাবাহিক নোডে সংরক্ষিত থাকে, এবং প্রতিটি নোড তার পরবর্তী নোডের সাথে যুক্ত থাকে। লিঙ্কড লিস্টের প্রতিটি নোডে দুটি প্রধান অংশ থাকে:

1. ডেটা অংশ: এখানে উপাদানের মান সংরক্ষিত থাকে।
2. পরবর্তী অংশ (Next/Pointer): এটি পরবর্তী নোডের ঠিকানা ধারণ করে।

লিঙ্কড লিস্টের প্রধান সুবিধা হলো এটি ডায়নামিক মেমরি ব্যবস্থাপনা সমর্থন করে, যার মাধ্যমে সহজে নতুন উপাদান যোগ বা মুছে ফেলা যায়। অ্যারের মতো পূর্বনির্ধারিত আকারের প্রয়োজন হয় না।

লিঙ্কড লিস্টের প্রকারভেদ

লিঙ্কড লিস্ট সাধারণত তিন প্রকারের হয়ে থাকে:

1. সিঙ্গলি লিঙ্কড লিস্ট (Singly Linked List)
2. ডাবলি লিঙ্কড লিস্ট (Doubly Linked List)
3. সার্কুলার লিঙ্কড লিস্ট (Circular Linked List)

১. সিঙ্গলি লিঙ্কড লিস্ট (Singly Linked List)

সিঙ্গলি লিঙ্কড লিস্ট হলো সবচেয়ে সহজ লিঙ্কড লিস্ট প্রকার যেখানে প্রতিটি নোড শুধুমাত্র পরবর্তী নোডের ঠিকানা ধারণ করে। এটি শুধুমাত্র একদিকে চলতে পারে।

বৈশিষ্ট্য:

• প্রতিটি নোডে একটি ডেটা অংশ এবং একটি পরবর্তী নোডের পয়েন্টার থাকে।
• প্রথম নোডকে হেড (Head) বলা হয়, এবং এটি লিঙ্কড লিস্টের সূচনা।
• শেষ নোডের পয়েন্টার NULL হয়, কারণ এর পর কোন নোড নেই।

উদাহরণ (C++):

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* next;
};

int main() {
    Node* head = new Node(); // হেড নোড তৈরি করা
    head->data = 1;
    head->next = new Node(); // দ্বিতীয় নোড তৈরি করা
    head->next->data = 2;
    head->next->next = NULL; // শেষ নোড, তাই পরবর্তী NULL

    // লিস্ট প্রদর্শন করা
    Node* current = head;
    while (current != NULL) {
        cout << current->data << " ";
        current = current->next;
    }

    return 0;
}

২. ডাবলি লিঙ্কড লিস্ট (Doubly Linked List)

ডাবলি লিঙ্কড লিস্ট হলো এমন একটি লিঙ্কড লিস্ট যেখানে প্রতিটি নোডে একটি ডেটা অংশ, একটি পরবর্তী নোডের পয়েন্টার এবং একটি পূর্ববর্তী নোডের পয়েন্টার থাকে। এটি উভয় দিকে চলতে পারে।

বৈশিষ্ট্য:

• প্রতিটি নোডে একটি Prev এবং একটি Next পয়েন্টার থাকে।
• প্রথম নোডের পূর্ববর্তী পয়েন্টার NULL হয় এবং শেষ নোডের পরবর্তী পয়েন্টার NULL হয়।
• উভয় দিকে লিস্ট ট্রাভার্স করা যায়।

উদাহরণ (C++):

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* next;
    Node* prev;
};

int main() {
    Node* head = new Node();
    head->data = 1;
    head->next = new Node();
    head->next->prev = head;
    head->next->data = 2;
    head->next->next = NULL;

    // ডাবলি লিঙ্কড লিস্ট প্রদর্শন করা
    Node* current = head;
    while (current != NULL) {
        cout << current->data << " ";
        current = current->next;
    }

    return 0;
}

৩. সার্কুলার লিঙ্কড লিস্ট (Circular Linked List)

সার্কুলার লিঙ্কড লিস্ট এমন একটি লিঙ্কড লিস্ট যেখানে শেষ নোডের পয়েন্টার প্রথম নোডের দিকে নির্দেশ করে। এটি একটি চক্র তৈরি করে, যাতে কোনও নির্দিষ্ট শেষ নেই।

বৈশিষ্ট্য:

• সিঙ্গলি এবং ডাবলি লিঙ্কড লিস্ট উভয়ের মতোই হতে পারে।
• শেষ নোডের পরবর্তী পয়েন্টার প্রথম নোডকে নির্দেশ করে, ফলে পুরো লিস্ট ঘুরতে থাকে।

উদাহরণ (C++):

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* next;
};

int main() {
    Node* head = new Node();
    head->data = 1;
    head->next = new Node();
    head->next->data = 2;
    head->next->next = head;  // শেষ নোডটি প্রথম নোডকে নির্দেশ করে

    // সার্কুলার লিঙ্কড লিস্ট প্রদর্শন করা (সতর্কতাঃ সীমিত প্রদর্শন)
    Node* current = head;
    int count = 0;
    do {
        cout << current->data << " ";
        current = current->next;
        count++;
    } while (current != head && count < 5);

    return 0;
}

লিঙ্কড লিস্টের তুলনামূলক বৈশিষ্ট্য

উপসংহার

লিঙ্কড লিস্ট ডেটা সংরক্ষণ এবং পরিচালনার একটি কার্যকর ডেটা স্ট্রাকচার, যা ডায়নামিক মেমরি ব্যবস্থাপনা এবং ডেটা অ্যাক্সেসকে সহজ করে। সিঙ্গলি, ডাবলি এবং সার্কুলার লিঙ্কড লিস্টের প্রতিটি প্রকার বিভিন্ন পরিস্থিতিতে কার্যকর ভূমিকা পালন করে, এবং তাদের বৈশিষ্ট্য অনুসারে বিভিন্ন কাজে ব্যবহার করা হয়।